package oj;

public class LC32 {
    //计算左括号和右括号的数量(不需要创建额外的空间)
    public int longestValidParentheses (String s) {
        int left=0,right=0,maxLen=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                left++;
            }else{
                right++;
            }
            if(left==right){
                maxLen=Math.max(left*2,maxLen);
            }
            if(right>left){
                left=right=0;
            }
        }
        left=0;
        right=0;
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='('){
                left++;
            }else{
                right++;
            }
            if(left==right){
                maxLen=Math.max(left*2,maxLen);
            }
            if(left>right){
                left=right=0;
            }
        }
        return maxLen;
    }

    //动态规划(需要创建一个dp数组)
//    public int longestValidParentheses (String s) {
//        // write code here
//        int n=s.length();
//        int maxLen=0;
//        int[] dp=new int[n];
//        for(int i=1;i<n;i++){
//            if(s.charAt(i)==')'){
//                if(s.charAt(i-1)=='('){
//                    dp[i]=(i>=2?dp[i-2]:0)+2;
//                }else if(i-dp[i-1]>0 && s.charAt(i-dp[i-1]-1)=='('){
//                    dp[i]=dp[i-1]+2+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0);
//                }
//                maxLen=Math.max(maxLen,dp[i]);
//            }
//        }
//        return maxLen;
//    }
}
